package sort.insert;

import common.tools.Sort;

/**
 * 插入排序：在数组中寻找一个标记（空位），标记左边已是局部有序的，只需将右边的数据与左边进行排序；
 * 			比较次数为N*(N-1)/2，执行时间O(N²)，但是比冒泡排序快一倍，比选择排序还要快
 * @Author  zhr
 * @Date  2012-6-11
 */
public class InsertSort implements Sort {

	/*  
	 * Override Method
	 * @see common.tools.Sort#doSort(int[])
	 */
	public void doSort(int[] array) {
		int temp = -1;
		int j = 0;
		//外层循环从1开始
		for(int i=1;i<array.length;i++){
			//交换变量是必须的
			temp = array[i];
			j = i;
			while(j>0 && array[j-1] > temp){
				array[j] = array[j-1];
				--j;
			}
			array[j] = temp;
		}
	}

	/*  
	 * Override Method
	 * @see common.tools.Sort#print(int[])
	 */
	public void print(int[] array) {
		System.out.println();
		for(int i:array){
			System.out.print(i+",");
		}
	}

}
